Дата је квадратна матрица \(A\) димензије \(N\), која представља директне авионске везе између \(N\) градова. Елемент \(a_{i,j}\) је једнак један ако постоји директан лет из града \(i\) за град \(j\), а нула иначе.

Одредити и исписати матрицу исте димензије, која приказује везе између истих градова уз највише једно преседање. Сматрати да је сваки град у директној вези са самим собом, без обзира на улазне вредности.

Улаз

У првом реду стандардног улаза налази се број \(N\), број градова (\(1 \leq N \leq 10\)). У наредних \(N\) редова налази се низ од \(N\) нула или јединица. Јединица у реду \(i\) на месту \(j\) значи да постоји директан лет од града \(i\) до града \(j\), а нула да не постоји.

Излаз

На стандардни излаз исписати \(N\) редова, у сваком по једну врсту резултујуће матрице. Елемент на позицији \((i, j)\) резултујуће матрице једнак је 1 ако постоји директна веза, или веза са једним преседањем између одговарајућих градова, а 0 иначе.

Пример

Улаз

4
0 1 0 1
1 0 0 0
1 1 0 0
0 0 1 0

Излаз

1 1 1 1
1 1 0 1
1 1 1 1
1 1 1 1

Објашњење

Из првог у трећи град се стиже преко четвртог града.

Из другог у четврти град се стиже преко првог града.

Из трећег у четврти град се стиже преко првог града.

Из четвртог у први град се стиже преко трећег града.

Из четвртог у други град се стиже преко трећег града.